﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.GeneralizedCoinChange.QuantityAndSizeModeling
{
    public class DynamicCoinChanger : SpaceSavingDynamicCoinChanger
    {
        private readonly DataStructures.Lists.IList<int> _values;
        private readonly int _n;
        private readonly DataStructures.Lists.IList<double> _weights;
        private readonly Func<IEnumerable<KeyValuePair<Tuple<int, int>, Tuple<int, int>>>, IBacktracer<Tuple<int, int>, int>> _createBacktracer;
        private readonly Func<IMap<Tuple<int, int>, double>> _createMap;
        private readonly Func<IMap<Tuple<int, int>, Tuple<int, int>>> _createBackpointersMap;

        public DynamicCoinChanger(DataStructures.Lists.IList<int> values, DataStructures.Lists.IList<double> weights = null,
            Func<IMap<Tuple<int,int>,double>> createMap = null,
            Func<IMap<Tuple<int,int>,Tuple<int,int>>> createBackpointersMap = null,
            Func<IEnumerable<KeyValuePair<Tuple<int,int>,Tuple<int,int>>>,IBacktracer<Tuple<int,int>,int>> createBacktracer = null)
            : base(values,weights)
        {
            _values = values;
            _n = values.Count;
            _weights = weights ?? Enumerable.Repeat(1.0,_n).ToAlgoritmiaList();
            _createMap = createMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, double>.Default);
            _createBackpointersMap = createBackpointersMap ?? (() => AlgoritmiaFactory.Maps<Tuple<int, int>, Tuple<int, int>>.Default);
            _createBacktracer = createBacktracer ?? (it => new DynamicBacktracer<Tuple<int, int>, int>(it));
        }

        public IEnumerable<int> Change(int Q)
        {
            var mem = _createMap();
            var firstCall = new Tuple<int, int>(0, 0);
            mem[firstCall] = 0.0;

            for (int q = 1; q <= Q; q++)
            {
                mem[new Tuple<int, int>(q, 0)] = double.PositiveInfinity;
            }
            var back = _createBackpointersMap();
            back[firstCall] = firstCall;

            for (int n = 1; n <= _n; n++)
            {
                for (int q = 0; q <= Q; q++)
                {
                    var i1 =
                        Enumerable.Range(0, (q / _values[n - 1]) + 1).ArgMin(
                            i => mem[new Tuple<int, int>(q - i * _values[n - 1], n - 1)] + i * _weights[n - 1]);
                    var currentCall = new Tuple<int, int>(q, n);
                    mem[currentCall] = mem[new Tuple<int, int>(q - i1 * _values[n - 1], n - 1)] +
                                                     i1 * _weights[n-1];
                    back[currentCall] = new Tuple<int, int>(q - i1 * _values[n-1], n - 1);
                }
            }
            return _createBacktracer(back).Backtrace(new Tuple<int, int>(Q, _n), (e, b) => (e.Item1 - b[e].Item1) / _values[e.Item2-1]);
        }

    }
}
